package 剑指offer;

import cn.hutool.core.util.ArrayUtil;
import lombok.Data;

import java.util.*;
import java.util.function.IntConsumer;

/**
 * @author: yangwk
 * @date: 2023/10/19
 * @description:
 **/
public class 最长广播响应 {
    @Data
    static class Edge {
        int start;
        int end;
        int distance;
    }

    @Data
    static class Graph {
        int V;
        int E = 0;
        List<List<Edge>> list = new ArrayList<>();

        public Graph(int v) {
            list.add(new ArrayList<>());
            for (int i = 1; i <= v; i++) {
                List<Edge> edgeList = new ArrayList<>();
                list.add(edgeList);
            }
        }

        public void addEdge(int start, int end) {
            List<Edge> startList = list.get(start);
            List<Edge> endList = list.get(end);
            Edge edge1 = new Edge();
            edge1.setStart(start);
            edge1.setEnd(end);
            Edge edge2 = new Edge();
            edge2.setStart(end);
            edge2.setEnd(start);
            startList.add(edge1);
            endList.add(edge2);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(7);
        graph.addEdge(5, 7);
        graph.addEdge(2, 1);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);
//        System.out.println(dfs(graph, 2));
        path = new int[8];
        bfs(graph, 2, 7);
//        pathTo(0, 7);
//        if (hasPathTo(7)) {
//            for (Integer x : pathTo(7, 2)) {
//                if (x != 2) {
//                    System.out.print(x + "-");
//                } else if (x == 2) {
//                    System.out.println(x);
//                }
//            }
//
//        }
    }

    static boolean[] visited = new boolean[100];
    static boolean find = false;

    public static int dfs(Graph g, int start) {
        visited[start] = true;
        int max = 0;
        for (Edge edge : g.list.get(start)) {
            if (!visited[edge.getEnd()]) {
                System.out.println(edge.getStart() + "->" + edge.getEnd());
                max = Math.max(dfs(g, edge.getEnd()), max) + 1;
            }
        }
        return max;
    }

    static int[] path;

    public static void bfs(Graph g, int start, int end) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start] = true;
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                Integer poll = queue.poll();
                for (Edge edge : g.list.get(poll)) {
                    if (!visited[edge.getEnd()]) {
                        visited[edge.getEnd()] = true;
                        path[edge.getEnd()] = poll;
                        System.out.println(edge.getStart() + "->" + edge.getEnd());
                        queue.offer(edge.getEnd());
                    }

                }
            }
            count++;

        }
        System.out.println(count * 2);
    }

    public static Iterable<Integer> pathTo(int v, int start) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        for (int x = v; x != start; x = path[x]) {
            stack.push(x);
        }
        stack.push(start);
        return stack;
    }

    public static boolean hasPathTo(int v) {
        return visited[v];
    }
}
